#include <atomic>
#include <chrono>
#include <cstdint>
#include <thread>
#include <iostream>
#include <vector>
#include <stdexcept>

class SlidingWindowLimiter {
public:
    using clock = std::chrono::steady_clock;

    SlidingWindowLimiter(uint64_t window_size_ms, uint64_t capacity, uint64_t slot_size_ms = 100)
        : window_size_ms_(window_size_ms),
          capacity_(capacity),
          slot_size_ms_(slot_size_ms),
          slot_id_(0),
          cur_count_(0),
          prev_count_(0)
    {
        if (window_size_ms == 0 || capacity == 0 || slot_size_ms == 0)
            throw std::invalid_argument("window_size, capacity, slot_size must be > 0");

        slot_id_.store(current_slot(), std::memory_order_relaxed);
    }

    bool try_acquire(uint64_t n = 1) {
        if (n == 0) return true;

        auto now = clock::now();
        uint64_t now_slot = current_slot(now);
        uint64_t w = slot_id_.load(std::memory_order_acquire);

        if (now_slot == w) {
            // 同一个 slot
            uint64_t prev = cur_count_.fetch_add(n, std::memory_order_acq_rel);
            if (estimate(now) <= capacity_) {
                return true;
            } else {
                cur_count_.fetch_sub(n, std::memory_order_acq_rel);
                return false;
            }
        } else if (now_slot > w) {
            // 跨 slot，需要推进
            if (slot_id_.compare_exchange_strong(w, now_slot,
                                                 std::memory_order_acq_rel,
                                                 std::memory_order_acquire)) {
                // 我是第一个推进 slot 的线程
                prev_count_.store(cur_count_.load(std::memory_order_relaxed),
                                  std::memory_order_relaxed);
                cur_count_.store(0, std::memory_order_relaxed);

                // 加上当前请求
                cur_count_.fetch_add(n, std::memory_order_relaxed);
                return estimate(now) <= capacity_;
            } else {
                // 有别的线程推进了，重试
                return try_acquire(n);
            }
        } else {
            // now_slot < w（几乎不会发生）
            return false;
        }
    }

    // 当前窗口估算的请求数
    double estimate(clock::time_point now = clock::now()) const {
        uint64_t cur = cur_count_.load(std::memory_order_relaxed);
        uint64_t prev = prev_count_.load(std::memory_order_relaxed);
        uint64_t now_slot = current_slot(now);

        uint64_t slot_start = now_slot * slot_size_ms_;
        uint64_t now_ms = std::chrono::duration_cast<std::chrono::milliseconds>(
                              now.time_since_epoch())
                              .count();
        double ratio = 1.0 - (double)(now_ms - slot_start) / slot_size_ms_;
        if (ratio < 0) ratio = 0;
        if (ratio > 1) ratio = 1;

        return cur + prev * ratio;
    }

private:
    uint64_t current_slot(clock::time_point t = clock::now()) const {
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(
                      t.time_since_epoch())
                      .count();
        return ms / slot_size_ms_;
    }

    const uint64_t window_size_ms_;
    const uint64_t capacity_;
    const uint64_t slot_size_ms_;

    std::atomic<uint64_t> slot_id_;
    std::atomic<uint64_t> cur_count_;
    std::atomic<uint64_t> prev_count_;
};

// ======================= 示例 =======================
int main() {
    SlidingWindowLimiter limiter(1000 /*1s窗口*/, 10 /*容量*/, 100 /*slot=100ms*/);

    constexpr int kThreads = 4;
    constexpr int kOpsPerThread = 20;
    std::atomic<int> success{0}, fail{0};

    std::vector<std::thread> ths;
    for (int i = 0; i < kThreads; ++i) {
        ths.emplace_back([&]() {
            for (int j = 0; j < kOpsPerThread; ++j) {
                if (limiter.try_acquire()) {
                    success.fetch_add(1, std::memory_order_relaxed);
                } else {
                    fail.fetch_add(1, std::memory_order_relaxed);
                }
                std::this_thread::sleep_for(std::chrono::milliseconds(50));
            }
        });
    }

    for (auto &t : ths) t.join();

    std::cout << "Success=" << success.load() << ", Fail=" << fail.load() << "\n";
    return 0;
}
